1. Field of the Invention
The present invention relates to a set-associative cache memory, and more particularly to a cache control that is configured to enable dynamic control of the cache capacity that is caused to operate.
2. Description of the Related Art
In microprocessors in recent years, the capacity of a cache memory that is mounted on a chip has been increasing rapidly to improve performance. As a consequence, of the power consumed by a microprocessor, the proportion that is consumed by the cache memory is also expanding rapidly.
On the other hand, programs that are executed by microprocessors have a wide variety of characteristics, and the capacity of the cache memory that is required by the characteristics of these programs also varies. Thus, not all programs will require all of the cache memory that is on a chip. Methods have therefore been proposed for reducing the power consumption of the microprocessor by controlling the capacity of cache memory such that only the necessary capacity of cache memory is caused to function and the remaining cache memory is halted.
As a typical configuration of cache memory, the set-associative system is in wide use. In the set-associative system, the cache memory is divided into a plurality of units called “ways,” tags and data being stored in each way. In such a configuration, controlling the number of ways that are caused to function enables control of the capacity of the cache memory. In other words, only the necessary number of ways is caused to function, and the supply of power or clocks may be halted to the other ways.
As a method of controlling the number of ways that are caused to operate in such cases, methods have been proposed in which the number of ways is controlled based on the cache miss rate (for example, refer to Japanese Patent Laid-Open Publication No. H9-50401). According to Japanese Patent Laid-Open Publication No. H9-50401, the cache miss rate is measured, the number of ways that are necessary is determined based on change in the cache miss rate, and the increase or decrease of the number of ways thus determined. Because the capacity of cache memory that is operated is dynamically controlled, power consumption in the cache memory can be more greatly reduced than when constantly operating all of the cache memory.
Alternatively, a cache system has also been proposed for improving the performance of cache memory by adopting a configuration that accords with the nature of a program. In this system, the optimum block configuration is determined during compilation, and this configuration then used during execution (for example, refer to Japanese Patent Laid-Open Publication No. 2000-20396).
However, the above-described prior art has the following problems:
The cache memory control method of the prior art such as is proposed in Japanese Patent Laid-Open Publication No. H9-50401 determines increase or decrease of the capacity of cache memory in accordance with the cache miss rate. However, the measured cache miss rate in some cases does not necessarily indicate the degree to which increasing cache capacity will bring about a reduction of the cache miss rate or the degree to which decreasing the cache capacity will affect the cache miss rate.
The access patterns of programs include patterns exhibiting a tendency to repeatedly and frequently access the same addresses or a tendency to access a variety of different addresses.
FIG. 1 presents graphs showing the access patterns of programs, FIG. 1A showing an access pattern in which the same addresses are repeatedly and frequently accessed, and FIG. 1B showing an access pattern in which a variety of different addresses are accessed. In FIG. 1, the LRU (Least Recently Used) state value indicates the degree of access to recently accessed ways, a lower value indicating a more recent access.
As shown in FIG. 1B, increasing the number of ways is effective when the cache miss rate is high in a program having a tendency to access a variety of different addresses. In contrast, in a program having a tendency to repeatedly and frequently access the same addresses as shown in FIG. 1A, the probability of access hits is low in ways having a low access frequency, and as a result, a further increase in the number of operated ways in response to a high cache miss rate will have little effect on decreasing the cache miss rate. In the cache memory control method of the prior art, control is implemented for increasing the number of ways even when this increase will have little effect on decreasing the cache miss rate.
Although a typical program exhibits a tendency (access pattern) in which cache access behaves with a certain degree of uniformity, because a program is made up of a combination of a variety of processes, the program will at times also exhibit behavior that diverges from the access pattern. In the cache memory control method of the prior art, when the cache miss rate changes due to this temporary behavior, the cache capacity was varied in accordance with these changes. However, changing the cache capacity in accordance with temporary behavior will result in a shortage or surplus of cache capacity when the behavior reverts to the original access pattern.
Thus, in the cache memory control methods of the prior art, it has been difficult to implement optimum control of the cache memory capacity that both improves cache performance and effectively reduces power consumption.
A prior-art cache system such as the one proposed in Japanese Patent Laid-Open Publication No. 2000-20396 includes cases in which the cache configuration is selected during compilation of the program. However, because the actual execution path is not known at the time of compilation, it is difficult to predict by static analysis the optimum cache configuration of the program during execution, and the system of Patent Laid-Open Publication No. 2000-20396 therefore may not be able to provide the optimum cache configuration of a program during execution and thus cannot improve cache performance.